Graphe d'Erdős-Rényi \(\mathcal G(n,p)\)
Graphe sur \(n\) noeuds \(i\in[\![1,n]\!]\) non orientés dans lequel la présence d'arêtes entre chaque noeud est dénotée par des
v.a. \(\xi_{i,j}\sim\mathcal{Ber}(p)\) indépendantes.
- on peut construire un Processus de Reed-Frost sur ce graphe en partant d'un ensemble \(X(0)\) de sommets initialement infectés, et en propageant l'infection via la relation de récurrence : $$\begin{align} X(t)&=\{i\in[\![1,n]\!]\setminus\ (X(0)\cup\dots\cup X(t-1))\mid \exists j\in X(t-1),\xi_{i,j}=1\}\\ &=\{i\in[\![1,n]\!]\mid d_G(X(0),i)=t\}\end{align}$$
- l'étendue finale de l'épidémie est donc la plus petite union de Composante connexes du graphe qui contient \(X(0)\)
- cela motive l'étude des Composante géantes
